// 回溯思想（不就是枚举吗，不行再回退）
/*
回溯的处理思想，有点类似枚举搜索。我们枚举所有的解，找到满足期望的解。
为了有规律地枚举所有可能，我们先随意选一条路走，当发现这条路走不通的时候，就回退到上一个岔路口，另选一种走法继续走。

大部分情况下，都是用来解决广义的搜索问题，也就是，从一组可能的解中，选择出一个满足要求的解。
回溯算法非常适合用递归来实现，在实现的过程中，剪枝操作是提高回溯效率的一种技巧。
剪枝：在不符合条件的情况下尽早结束该路劲的遍历。
*/

// 应用：深度优先搜索、八皇后、0-1背包问题、图的着色、旅行商问题、数独、全排列、正则表达式匹配等等

// 八皇后问题
/*
我们有一个8x8的棋盘，希望往里放8个棋子（皇后），每个棋子所在的行、列、对角线都不能有另一个棋子。
八皇后问题就是期望找到所有满足这种要求的放棋子方式。
*/
#include <iostream>
using std::cout;
using std::endl;

class Queens {
 public:
  Queens() {
    for (int i = 0; i < 8; ++i) {
      arr_[i] = -1;
    }
  }

  // void Cal8Queens(int row) {
  //   if (row >= 8) {
  //     Print();
  //   }
  //   bool canPut = false;
  //   // 从上往下一行一行放
  //   for (int col = 0; col < 8; ++col) {
  //     if (IsOk(row, col)) {
  //       arr_[row] = col;
  //       canPut = true;
  //       break; // 不能break呀，要是这一步走不通呢？还得回溯，然后走下一条路
  //     }
  //   }
  //   if (canPut) Cal8Queens(row + 1);
  // }

  void Cal8Queens(int row) {
    if (row >= 8) {
      Print();
    }
    bool canPut = false;
    for (int col = 0; col < 8; ++col) {
      if (IsOk(row, col)) {
        arr_[row] = col;
        Cal8Queens(row + 1);  // 有ok的列就继续放下一行
      }
    }
  }

  void Print() {
#if 1
    for (int i = 0; i < 8; ++i) {  // row
      for (int j = 0; j < arr_[i]; ++j) cout << " 0";
      cout << " *";
      for (int j = arr_[i] + 1; j < 8; ++j) cout << " 0";
      cout << endl;
    }
    cout << "-----------------" << endl;
#else
    for (int i = 0; i < 8; ++i) {
      cout << arr_[i] << ' ';
    }
    cout << endl;
#endif
  }

 private:
  // 如果比较复杂脑子转不过来，就拆分一个辅助函数（每次解决一个子问题）
  bool IsOk(int row, int col) {
    int leftupCol = col - 1;
    int rightupCol = col + 1;
    // 从上一行依次往上比较
    for (int i = row - 1; i >= 0; --i) {
      if (arr_[i] == col) {
        return false;
      }
      if (leftupCol >= 0 && arr_[i] == leftupCol) {
        return false;
      }
      if (rightupCol <= 7 && arr_[i] == rightupCol) {
        return false;
      }
      leftupCol--;
      rightupCol++;
    }
    return true;
  }

  int arr_[8];  // 下标为行，数据为列
};

void TestQueens() {
  Queens queens;
  queens.Cal8Queens(0);
}

// 正则表达式匹配
/*
?表示前面的内容出现0或1次       a? 0或1个a
*表示前面的内容出现任意次(>=0)  a* 0或任意个a

比如正则ab*ef，字符串abbbef
  先匹配abef 不对
  回溯匹配abbef 不对
  回溯匹配abbbef 对了
*/

int main() { TestQueens(); }